Building on the fundamental pointer operation of advancing ($p = p.next$), traversal is the primary read operation on a Linked List, requiring us to visit every Node_Structure from the head to $NULL$.

  • Since we must examine all $n$ elements in the worst case, the time complexity for traversal is always $O(n)$, regardless of implementation.
  • Iterative Traversal (Loop-Based): Uses a temporary pointer, often $p$, initialized to the $head$. Continues execution using a `while` loop until $p$ becomes $NULL$.
  • Performance benefit: Avoids the overhead of function calls (unlike recursion).
  • Recursive Traversal (Call Stack-Based): The base case is reached when the current node is $NULL$.
  • The recursive step processes the current node and then calls itself on the $next$ pointer ($\text{recursive\_call}(\text{node.next})$).
  • This approach often leads to cleaner code, but may consume more stack space for very large $n$.

Complexity Summary

Both iterative and recursive traversal methods achieve the same goal: visiting all $n$ nodes sequentially. Therefore, the time complexity remains $O(n)$ for both.

The primary trade-off is between stack space (recursion) and explicit pointer management (iteration).